class Solution {
public:
    bool exist(vector<vector<char>>& board, string word) {
        int newsize=word.size()-1;
        int ws=0;
        vector<vector<bool>> visited(board.size(),vector<bool>(board[0].size(),false));
        
        for(int i=0;i<board.size();i++){
            for(int j=0;j<board[i].size();j++){
                if(lookdfs(board,word,visited,i,j,ws)){
                    return true;
                }
            }
        }
        return false;
    }
    bool lookdfs(vector<vector<char>>& board,string& word,vector<vector<bool>>& visited,int i,int j,int start){
        if(i<0||i>=board.size()||j<0||j>=board[0].size()||word[start]!=board[i][j]||visited[i][j]){
            return false;
        }
        if(start>=word.size()-1){
            return true;
        }
        visited[i][j]=true;
        bool ans=false;
        ans=lookdfs(board,word,visited,i+1,j,start+1)
            ||lookdfs(board,word,visited,i-1,j,start+1)
            ||lookdfs(board,word,visited,i,j+1,start+1)
            ||lookdfs(board,word,visited,i,j-1,start+1);
        visited[i][j]=false;
        return ans; 
    }
};
